package com.wispx.gateway.core.filter.loadblance.algorithm;

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 一致性hash算法
 */
public class ConsistentHashCircle {

    /**
     * 虚拟节点个数
     */
    private int virtualNodeNum;

    /**
     * 哈希环（TreeMap实现）
     */
    private SortedMap<Integer /* instanceName的hash值 */, String /* instanceName */> hashCircle;

    public ConsistentHashCircle(int virtualNodeNum, List<String> nodes) {
        this.virtualNodeNum = virtualNodeNum;
        this.hashCircle = new TreeMap<>();
        for (String node : nodes) {
            addNode(node);
        }
    }

    /**
     * 为实例添加虚拟节点
     *
     * @param node 实例名字
     */
    private void addNode(String node) {
        for (int i = 0; i < virtualNodeNum; i++) {
            String key = node + "&&VN" + i;
            hashCircle.put(getHash(key), key);
        }
    }

    public String getNode(String key) {
        if (hashCircle.isEmpty()) {
            return null;
        }
        int keyHash = getHash(key);
        SortedMap<Integer, String> tailMap = hashCircle.tailMap(keyHash); // 从Hash环上向后找
        int nodeHash = (tailMap == null || tailMap.isEmpty()) ?
                hashCircle.firstKey() : tailMap.firstKey();
        return hashCircle.get(nodeHash);
    }

    private int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

}
